package Midium;

//55.跳跃游戏
public class Solution55 {
    //答案思路
    public boolean canJump(int[] nums) {
        int far = nums[0];
        if (far == 0 && nums.length > 1)
            return false;
        while (far < nums.length - 1) {
            //可以走1到far步
            int oldFar = far;
            for (int i = 1; i <= oldFar; i++) {
                //走了i步以后，看看对于从i开始的位置能否更新far
                if (i + nums[i] > far) {
                    far = i + nums[i];
                }
            }
            if (oldFar == far)
                return false;
        }
        return true;
    }

    //我的思路
    public boolean myCanJump(int[] nums) {
        int step = 0;//step>=nums.length-1时结束，返回true
        return dfs(nums, step);
    }

    public boolean dfs(int[] nums, int step) {
        if (step < nums.length - 1) {
            for (int i = nums[step]; i > 0; i--) {
                int newStep = step + i;
                if (dfs(nums, newStep)) {
                    return true;
                }
            }
            return false;
        } else {
            //>=
            return true;
        }
    }

    public static void main(String[] args) {
        Solution55 s = new Solution55();
        System.out.println(s.canJump(new int[]{1,2,3}));
    }
}
